{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "17d679f8",
   "metadata": {},
   "source": [
    "### 试题 算法训练 预测身高"
   ]
  },
  {
   "cell_type": "raw",
   "id": "d6b8b434",
   "metadata": {},
   "source": [
    "资源限制\n",
    "时间限制：1.0s 内存限制：256.0MB\n",
    "问题描述：\n",
    "　　生理卫生老师在课堂上娓娓道来：\n",
    "　　你能看见你未来的样子吗？显然不能。但你能预测自己成年后的身高，有公式：\n",
    "　　男孩成人后身高=（父亲身高+母亲身高）/ 2 * 1.08\n",
    "　　女孩成人后身高=(父亲身高0.923+母亲身高）/ 2\n",
    "　　数学老师听见了，回头说：这是大样本统计拟合公式，准确性不错。\n",
    "　　生物老师听见了，回头说：结果不是绝对的，影响身高的因素很多，比如营养、疾病、体育锻炼、睡眠、情绪、环境因素等。\n",
    "　　老师们齐回头，看见同学们都正在预测自己的身高。\n",
    "　　毛老师见此情形，推推眼镜说：何必手算，编程又快又简单…\n",
    "　　约定：\n",
    "　　身高的单位用米表示，所以自然是会有小数的。\n",
    "　　男性用整数1表示，女性用整数0表示。\n",
    "　　预测的身高保留三位小数\n",
    "输入格式\n",
    "　　用空格分开的三个数，整数 小数 小数\n",
    "　　分别表示：性别 父亲身高 母亲身高\n",
    "输出格式\n",
    "　　一个小数，表示根据上述表示预测的身高（保留三位小数）\n",
    "样例输入\n",
    "1 1.91 1.70\n",
    "样例输出\n",
    "1.949\n",
    "样例输入\n",
    "0 1.00 2.077\n",
    "样例输出\n",
    "1.500\n",
    "数据规模和约定\n",
    "　　父母身高范围（0，3]\n",
    "　　时间限制1.0秒"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ba8b7c25",
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "sex, father_high, mother_high = map(float, input().split())\n",
    "\n",
    "if sex == 1:\n",
    "    print( '%.3f' % ((father_high + mother_high) / 2 * 1.08) )\n",
    "\n",
    "if sex == 0:\n",
    "    print( '%.3f' % (( father_high * 0.923 + mother_high) / 2) )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ac363e1",
   "metadata": {},
   "source": [
    "### 试题 算法训练 1的个数"
   ]
  },
  {
   "cell_type": "raw",
   "id": "40436c4a",
   "metadata": {},
   "source": [
    "问题描述\n",
    "　　输入正整数n，判断从1到n之中，数字1一共要出现几次。例如1123这个数，则出现了两次1。例如15，那么从1到15之中，一共出现了8个1。\n",
    "输入格式\n",
    "　　一个正整数n\n",
    "输出格式\n",
    "　　一个整数，表示1出现的资料\n",
    "样例输入\n",
    "15\n",
    "样例输出\n",
    "8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "48a0b58d",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = int(input())\n",
    "ans = 0\n",
    "for i in range(1, n+1):\n",
    "    strn = str(i)\n",
    "    ans += strn.count('1')\n",
    "print(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e84784b1",
   "metadata": {},
   "source": [
    "### 试题 算法训练 最小公倍数"
   ]
  },
  {
   "cell_type": "raw",
   "id": "58536b73",
   "metadata": {},
   "source": [
    "问题描述\n",
    "　　编写一函数lcm，求两个正整数的最小公倍数。\n",
    "样例输入\n",
    "一个满足题目要求的输入范例。\n",
    "例：\n",
    "\n",
    "3 5\n",
    "样例输出\n",
    "15"
   ]
  },
  {
   "cell_type": "raw",
   "id": "0ecb1ad9",
   "metadata": {},
   "source": [
    "最小公倍数 lcm = a*b/gcd(a,b)\n",
    "\n",
    "gcd为最大公约数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4f1ad042",
   "metadata": {},
   "outputs": [],
   "source": [
    "def gcd(num_1, num_2):\n",
    "    result = num_1 % num_2\n",
    "    while result != 0:\n",
    "        num_1 = num_2 \n",
    "        num_2 = result\n",
    "        result = num_1 % num_2\n",
    "    \n",
    "    return num_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7759c5ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "def gcd(num_1, num_2):\n",
    "    result = num_1 % num_2\n",
    "    while result != 0:\n",
    "        num_1 = num_2 \n",
    "        num_2 = result\n",
    "        result = num_1 % num_2\n",
    "    \n",
    "    return num_2\n",
    "\n",
    "num_1, num_2 = map(int, input().split())\n",
    "\n",
    "print(num_1 * num_2 // gcd(num_1, num_2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "675df4a2",
   "metadata": {},
   "source": [
    "### 试题 算法训练  递归求二项式系数值"
   ]
  },
  {
   "cell_type": "raw",
   "id": "900ba407",
   "metadata": {},
   "source": [
    "资源限制\n",
    "时间限制：10.0s 内存限制：256.0MB\n",
    "在这里插入图片描述\n",
    "样例输入\n",
    "一个满足题目要求的输入范例。\n",
    "3 10\n",
    "样例输出\n",
    "与上面的样例输入对应的输出。\n",
    "\n",
    "数据规模和约定\n",
    "　　输入数据中每一个数的范围。\n",
    "　　例：结果在int表示时不会溢出。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5079d987",
   "metadata": {},
   "source": [
    "### 递归写法！！！"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "956b0145",
   "metadata": {},
   "outputs": [],
   "source": [
    "def C(k,n):\n",
    "    if k == n or k == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return C(k, n-1) + C(k-1,n-1)\n",
    "\n",
    "k,n = map(int, input().split())\n",
    "\n",
    "print(C(k,n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c27b290d",
   "metadata": {},
   "source": [
    "### 试题 算法训练 k好数"
   ]
  },
  {
   "cell_type": "raw",
   "id": "a82c2a08",
   "metadata": {},
   "source": [
    "资源限制\n",
    "\n",
    "时间限制：1.0s 内存限制：256.0MB\n",
    "问题描述\n",
    "\n",
    "如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值。\n",
    "输入格式\n",
    "\n",
    "输入包含两个正整数，K和L。\n",
    "输出格式\n",
    "\n",
    "输出一个整数，表示答案对1000000007取模后的值。\n",
    "样例输入\n",
    "\n",
    "    4 2\n",
    "\n",
    "样例输出\n",
    "\n",
    "    7\n",
    "\n",
    "数据规模与约定\n",
    "\n",
    "对于30%的数据，KL <= 106；\n",
    "\n",
    "对于50%的数据，K <= 16， L <= 10；\n",
    "\n",
    "对于100%的数据，1 <= K,L <= 100。"
   ]
  },
  {
   "cell_type": "raw",
   "id": "ae7b13fa",
   "metadata": {},
   "source": [
    "如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。\n",
    "求L位K进制数中K好数的数目"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "901104ec",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "K, L = map(int, input().split())\n",
    "\n",
    "dp = [[0 for _ in range(L+1)] for _ in range(K)]\n",
    "\n",
    "print(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "68821d6a",
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(K):\n",
    "    dp[i][1] = 1\n",
    "    \n",
    "print(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "17da9488",
   "metadata": {},
   "outputs": [],
   "source": [
    "mod = 1000000007\n",
    "for i in range(2, L+1): # 按列遍历 L表示L位数\n",
    "    for j in range(K):  # 按行遍历\n",
    "        for w in range(K):\n",
    "            if w != j+1 and w != j-1: # 相邻的数字不添加\n",
    "                dp[j][i] = (dp[j][i] + dp[w][i-1])%mod\n",
    "                \n",
    "print(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ad575202",
   "metadata": {},
   "outputs": [],
   "source": [
    "ans = 0\n",
    "# 将第L列的数字相加即为ans\n",
    "for i in range(1,K):\n",
    "    ans = (ans + dp[i][L])%mod\n",
    "    \n",
    "print(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f1b65ef",
   "metadata": {},
   "source": [
    "### 试题 算法训练 最大的算式"
   ]
  },
  {
   "cell_type": "raw",
   "id": "4a951f07",
   "metadata": {},
   "source": [
    "问题描述\n",
    "　　题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如：\n",
    "　　N=5，K=2，5个数字分别为1、2、3、4、5，可以加成：\n",
    "　　1*2*(3+4+5)=24\n",
    "　　1*(2+3)*(4+5)=45\n",
    "　　(1*2+3)*(4+5)=45\n",
    "　　……\n",
    "输入格式\n",
    "　　输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中（2<=N<=15, 0<=K<=N-1）。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。\n",
    "输出格式\n",
    "　　输出文件仅一行包含一个整数，表示要求的最大的结果\n",
    "样例输入\n",
    "5 2\n",
    "1 2 3 4 5\n",
    "样例输出\n",
    "120"
   ]
  },
  {
   "cell_type": "raw",
   "id": "d27e5d02",
   "metadata": {},
   "source": [
    "在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5aacddc0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 输入数据\n",
    "n, k = map(int, input().split())\n",
    "\n",
    "listq = list(map(int, input().split()))\n",
    "\n",
    "tmp = listq[0]\n",
    "# 建立dp数组\n",
    "dp = [[0 for _ in range(k+1)] for _ in range(n+1)]\n",
    "\n",
    "dp[1][0] = tmp #  提前将第一个数放入dp数组中,方便下面for循环放置\n",
    "\n",
    "# 将dp数组第一列数据添加\n",
    "for i in range(1, n):\n",
    "    tmp += listq[i]\n",
    "    dp[i+1][0] = tmp\n",
    "# 当没有乘号时\n",
    "if k == 0:\n",
    "    print(dp[n][k])\n",
    "else:\n",
    "    for j in range(1, k+1): # 按列循环\n",
    "        for i in range(2, n+1): # 按行循环\n",
    "            if i > j: # 乘号小于要计算的各个数字\n",
    "                '''\n",
    "                ①dp[5][1] = dp[1][0]x(dp[5][0] - dp[1][0]) = 14\n",
    "                ②dp[5][1] = dp[2][0]x(dp[5][0] - dp[2][0]) = 36\n",
    "                ③dp[5][1] = dp[3][0]x(dp[5][0] - dp[3][0]) = 54\n",
    "                ④dp[5][1] = dp[4][0]x(dp[5][0] - dp[4][0]) = 50\n",
    "                max函数取其中最大的得数\n",
    "                '''\n",
    "                for p in range(1,i):\n",
    "                    dp[i][j] = max(dp[i][j], dp[p][j-1]*(dp[i][0] - dp[p][0]))\n",
    "\n",
    "    print(dp[n][k])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0621e1d",
   "metadata": {},
   "source": [
    "### 试题 算法训练 石子游戏"
   ]
  },
  {
   "cell_type": "raw",
   "id": "a8ef77ce",
   "metadata": {},
   "source": [
    "问题描述\n",
    "　　石子游戏的规则如下：\n",
    "　　地上有n堆石子，每次操作可选取两堆石子（石子个数分别为x和y）并将它们合并，操作的得分记为(x+1)×(y+1)，对地上的石子堆进行操作直到只剩下一堆石子时停止游戏。\n",
    "　　请问在整个游戏过程中操作的总得分的最大值是多少？\n",
    "输入格式\n",
    "　　输入数据的第一行为整数n，表示地上的石子堆数；第二行至第n+1行是每堆石子的个数。\n",
    "输出格式\n",
    "　　程序输出一行，为游戏总得分的最大值。\n",
    "样例输入\n",
    "10\n",
    "5105\n",
    "19400\n",
    "27309\n",
    "19892\n",
    "27814\n",
    "25129\n",
    "19272\n",
    "12517\n",
    "25419\n",
    "4053\n",
    "样例输出\n",
    "15212676150"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0c006f3f",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "n = int(input())\n",
    "\n",
    "stones = [int(input()) for _ in range(n)]\n",
    "\n",
    "results = 0\n",
    "\n",
    "while len(stones) > 1:\n",
    "    max_1 = max(stones)\n",
    "    stones.remove(max_1)\n",
    "    max_2 = max(stones)\n",
    "    stones.remove(max_2)\n",
    "    \n",
    "    results = (max_1+1) * (max_2+1)\n",
    "    stones.append(max_1+max_2)\n",
    "    \n",
    "print(results)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56468555",
   "metadata": {},
   "source": [
    "### 试题 算法训练 Torry的困惑(基本型)"
   ]
  },
  {
   "cell_type": "raw",
   "id": "3a7cccf1",
   "metadata": {},
   "source": [
    "问题描述\n",
    "　　Torry从小喜爱数学。一天，老师告诉他，像2、3、5、7……这样的数叫做质数。Torry突然想到一个问题，前10、100、1000、10000……个质数的乘积是多少呢？他把这个问题告诉老师。老师愣住了，一时回答不出来。于是Torry求助于会编程的你，请你算出前n个质数的乘积。不过，考虑到你才接触编程不久，Torry只要你算出这个数模上50000的值。\n",
    "输入格式\n",
    "　　仅包含一个正整数n，其中n<=100000。\n",
    "输出格式\n",
    "　　输出一行，即前n个质数的乘积模50000的值。\n",
    "样例输入\n",
    "1\n",
    "样例输出\n",
    "2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "493255eb",
   "metadata": {},
   "outputs": [],
   "source": [
    "mod = 50000\n",
    "\n",
    "\n",
    "def judge(res_list, num):\n",
    "    \n",
    "    for i in range(2, num+1):\n",
    "        \n",
    "        if num % i ==0:\n",
    "            \n",
    "            res_list.append(i)\n",
    "            \n",
    "            num = num // i\n",
    "            \n",
    "            if num == 1:\n",
    "                \n",
    "                return res_list\n",
    "            \n",
    "            else:\n",
    "                    \n",
    "                return judge(res_list, num)\n",
    "            \n",
    "        else:\n",
    "            continue\n",
    "    \n",
    "n = int(input())\n",
    "\n",
    "nums = list()\n",
    "\n",
    "num = 2\n",
    "\n",
    "while len(nums) < n:\n",
    "    \n",
    "    res_list = list()\n",
    "    \n",
    "    judge(res_list, num)\n",
    "    \n",
    "    if len(res_list) == 1:\n",
    "        \n",
    "        nums.append(num)\n",
    "        \n",
    "    num += 1\n",
    "\n",
    "print(nums)\n",
    "\n",
    "\"\"\"\n",
    "from math import prod\n",
    "\n",
    "print(prod(nums))\n",
    "\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93b61a9c",
   "metadata": {},
   "source": [
    "### 试题 算法训练 最小乘积(基本型)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0330da52",
   "metadata": {},
   "outputs": [],
   "source": [
    "t = int(input())\n",
    "for _ in range(t):\n",
    "    ans = 0\n",
    "    n = int(input())\n",
    "    arr1 = list(map(int, input().split()))\n",
    "    arr2 = list(map(int, input().split()))\n",
    "\n",
    "    numList1 = sorted(arr1)  # 升序\n",
    "    numList2 = sorted(arr2, reverse=True)  # 降序\n",
    "    for i in range(n):\n",
    "        ans += numList1[i] * numList2[i]\n",
    "    print(ans)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "lanqiaobei",
   "language": "python",
   "name": "lanqiaobei"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
